package 链表;

import com.alibaba.fastjson.JSON;

public class NC53删除链表倒数第K个节点 {

    /**
     * 给定一个链表，删除链表的倒数第n个节点并返回链表的头指针
     * 例如，
     *  给出的链表为:1->2->3->4->5, n= 2.
     *  删除了链表的倒数第n个节点之后,链表变为1->2->3->5.
     * 备注：
     * 题目保证n一定是有效的
     * 请给出请给出时间复杂度为O(n)的算法
     */

    public ListNode removeNthFromEnd (ListNode head, int n) {

        ListNode fast=head;
        ListNode slow=head;

        while (n>0){
            fast=fast.next;
            n--;
        }

        ListNode last=head;

        while (fast!=null){
            fast=fast.next;
            last=slow;
            slow= slow.next;
        }

        last.next=slow.next;
        slow.next=null;

        return head;
    }

    public static void main(String[] args) {
        NC53删除链表倒数第K个节点 n=new NC53删除链表倒数第K个节点();
        ListNode listNode = ListNode.createListNode(new int[]{1, 2, 3, 4, 5, 6, 7, 8});
        ListNode result = n.removeNthFromEnd(listNode, 4);
        ListNode.printListNode(listNode);
    }

}
